{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Good Nodes in Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: goodNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计二叉树中好节点的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵根为&nbsp;<code>root</code>&nbsp;的二叉树，请你返回二叉树中好节点的数目。</p>\n",
    "\n",
    "<p>「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/16/test_sample_1.png\" style=\"height: 156px; width: 263px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [3,1,4,3,null,1,5]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>图中蓝色节点为好节点。\n",
    "根节点 (3) 永远是个好节点。\n",
    "节点 4 -&gt; (3,4) 是路径中的最大值。\n",
    "节点 5 -&gt; (3,4,5) 是路径中的最大值。\n",
    "节点 3 -&gt; (3,1,3) 是路径中的最大值。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/16/test_sample_2.png\" style=\"height: 161px; width: 157px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [3,3,null,4,2]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>节点 2 -&gt; (3, 3, 2) 不是好节点，因为 &quot;3&quot; 比它大。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>根节点是好节点。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树中节点数目范围是&nbsp;<code>[1, 10^5]</code>&nbsp;。</li>\n",
    "\t<li>每个节点权值的范围是&nbsp;<code>[-10^4, 10^4]</code>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-good-nodes-in-binary-tree](https://leetcode.cn/problems/count-good-nodes-in-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-good-nodes-in-binary-tree](https://leetcode.cn/problems/count-good-nodes-in-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,4,3,null,1,5]', '[3,3,null,4,2]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def goodNodes(self, root: TreeNode) -> int:\n",
    "        self.cnt = 0\n",
    "        \n",
    "        def dfs(root, maxSoFar):\n",
    "            if root is None:\n",
    "                return \n",
    "\n",
    "            if root.val >= maxSoFar:\n",
    "                self.cnt += 1\n",
    "                maxSoFar = root.val\n",
    "            \n",
    "            dfs(root.left, maxSoFar)\n",
    "            dfs(root.right, maxSoFar)\n",
    "            \n",
    "            return self.cnt\n",
    "        \n",
    "        return dfs(root, float('-inf'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def goodNodes(self, root: TreeNode) -> int:\n",
    "        nodes, vals = [root,],[root.val, ]\n",
    "        cnt = 1\n",
    "\n",
    "        while nodes:\n",
    "            curr = nodes[-1]\n",
    "            # print(vals)\n",
    "            if not curr.left and not curr.right:\n",
    "                nodes.pop()\n",
    "                vals.pop()\n",
    "            else:\n",
    "                left = curr.left\n",
    "                right = curr.right\n",
    "                if left:\n",
    "                    nodes[-1].left = None\n",
    "                    nodes.append(left)\n",
    "                    vals.append(left.val)\n",
    "                    if vals[-1]==max(vals):\n",
    "                        cnt +=1\n",
    "                elif right:\n",
    "                    nodes[-1].right = None\n",
    "                    nodes.append(right)\n",
    "                    vals.append(right.val)\n",
    "                    if vals[-1]==max(vals):\n",
    "                        cnt +=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def goodNodes(self, root: TreeNode) -> int:\n",
    "        self.count = 1\n",
    "        def recoursion(r):\n",
    "            if r.left:\n",
    "                if r.left.val >= r.val:\n",
    "                    self.count += 1\n",
    "                else:\n",
    "                    r.left.val = r.val\n",
    "                recoursion(r.left)\n",
    "            if r.right:\n",
    "                if r.right.val >= r.val:\n",
    "                    self.count += 1\n",
    "                else:\n",
    "                    r.right.val = r.val\n",
    "                recoursion(r.right)\n",
    "        recoursion(root)\n",
    "        return self.count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def goodNodes(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        ans=1\n",
    "        stack=[root]\n",
    "        while stack:\n",
    "            i=stack.pop(0)\n",
    "            if i.left:\n",
    "                stack.append(i.left)\n",
    "                if i.left.val>=i.val:\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    i.left.val=i.val\n",
    "            if i.right:\n",
    "                stack.append(i.right)\n",
    "                if i.right.val>=i.val:\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    i.right.val=i.val\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def goodNodes(self, root: TreeNode) -> int:\n",
    "        ans=1\n",
    "        queue = [root]\n",
    "        while len(queue)!=0:\n",
    "            root = queue.pop(0)\n",
    "            l=root.left\n",
    "            if l:\n",
    "                if root.val <= l.val:\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    l.val=root.val\n",
    "                queue.append(l)\n",
    "            r=root.right\n",
    "            if r:\n",
    "                if root.val <= r.val:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    r.val = root.val\n",
    "                queue.append(r)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#判断有多少节点从根到该节点的路径中没有经过比该节点大的数\n",
    "#全部遍历一遍肯定可以，也可以看作左右两边的后序\n",
    "class Solution:\n",
    "    def goodNodes(self, root: TreeNode) -> int:\n",
    "        def dfs(root,pre):\n",
    "            if root==None:return 0\n",
    "            pre.append(root.val)\n",
    "            l=dfs(root.left,pre)\n",
    "            r=dfs(root.right,pre)\n",
    "            pre.pop()\n",
    "            for n in pre:\n",
    "                if n>root.val:return l+r\n",
    "            return l+r+1\n",
    "        return dfs(root,[])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 1\n",
    "    def walk(self, node: TreeNode):\n",
    "        if node.left:\n",
    "            if node.left.val >= node.val:\n",
    "                self.res += 1\n",
    "            else:\n",
    "                node.left.val = node.val\n",
    "            self.walk(node.left)\n",
    "        if node.right:\n",
    "            if node.right.val >= node.val:\n",
    "                self.res += 1\n",
    "            else:\n",
    "                node.right.val = node.val\n",
    "            self.walk(node.right)\n",
    "            \n",
    "    def goodNodes(self, root: TreeNode) -> int:\n",
    "        self.res = 1\n",
    "        self.walk(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def goodNodes(self, root: TreeNode) -> int:\n",
    "        def goodnum(max_num,root):\n",
    "            if root.val <max_num:\n",
    "                num=0 \n",
    "                root.val=max_num\n",
    "            else: \n",
    "                num=1\n",
    "                max_num = root.val\n",
    "            if not root.left == None: num += goodnum(max_num,root.left)\n",
    "            if not root.right == None: num += goodnum(max_num,root.right)\n",
    "            return num\n",
    "        if root == None: return 0\n",
    "        else:\n",
    "            return goodnum(float(-inf), root)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def goodNodes(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root, maxValue):\n",
    "            if root is None:\n",
    "                return\n",
    "            if maxValue <= root.val:\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                maxValue = root.val\n",
    "            dfs(root.left, maxValue)\n",
    "            dfs(root.right, maxValue)\n",
    "        dfs(root, -inf)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def goodNodes(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(root, router):\n",
    "            router.append(root.val)\n",
    "            if root.val >= max(router):\n",
    "                nonlocal ans\n",
    "                ans += 1\n",
    "                print(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                router.pop()\n",
    "                return\n",
    "            if root.left:\n",
    "                dfs(root.left, router)\n",
    "            if root.right:\n",
    "                dfs(root.right, router)\n",
    "            router.pop()\n",
    "        \n",
    "        dfs(root, [])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "#思路:维护两个全局变量，maximum保存这条路上的最大值，等到叶子节点比较叶子节点和最大值 cnt保存好节点的数目 ...我写了一个好叶子节点个数。。\n",
    "# class Solution:\n",
    "#     def goodNodes(self, root: TreeNode) -> int:\n",
    "#         maximum = 0\n",
    "#         cnt = 0\n",
    "#         def recur(root):\n",
    "#             if root is None:\n",
    "#                 return\n",
    "#             nonlocal cnt,maximum\n",
    "#             if root.right is None and root.left is None:\n",
    "#                 if root.val>=maximum:\n",
    "#                     cnt+=1\n",
    "#                 maximum = 0\n",
    "#                 return\n",
    "#             maximum = max(maximum,root.val)\n",
    "#             recur(root.left)\n",
    "#             recur(root.right)\n",
    "        \n",
    "#         recur(root)\n",
    "#         return cnt       \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def goodNodes(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node,pre):\n",
    "            if not node:\n",
    "                return\n",
    "            nonlocal ans\n",
    "            if node.val>=pre:\n",
    "                ans+=1\n",
    "            dfs(node.left,max(node.val,pre))\n",
    "            dfs(node.right,max(node.val,pre))\n",
    "        dfs(root,-inf)\n",
    "        return ans\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def goodNodes(self, root: TreeNode, mx=-inf) -> int:\n",
    "#         if root is None:\n",
    "#             return 0\n",
    "#         left = self.goodNodes(root.left, max(mx, root.val))\n",
    "#         right = self.goodNodes(root.right, max(mx, root.val))\n",
    "#         return left + right + (mx <= root.val)\n",
    "\n",
    "\n",
    "\n",
    "  "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
